package main

import "go-leetcode/leetcode/utils"

//230. 二叉搜索树中第K小的元素
func main() {

}

func kthSmallest(root *utils.TreeNode, k int) int {
	// 用栈模拟中序遍历，先进后出
	if root == nil {
		return 0
	}

	var stack []*utils.TreeNode

	for k > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}

		// 逐个拿出栈的元素
		stack, root = stack[:len(stack)-1], stack[len(stack)-1]
		k--
		if k == 0 {
			return root.Val
		}
		root = root.Right
	}

	return 0
}

// 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
//
//示例 1：
//
//输入：root = [3,1,4,null,2], k = 1
//输出：1
//示例 2：
//
//输入：root = [5,3,6,2,4,null,null,1], k = 3
//输出：3
//
//提示：
//
//树中的节点数为 n 。
//1 <= k <= n <= 104
//0 <= Node.val <= 104
//
//进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
